Azure doesn't store private keys; it only has public keys. If you lost your private key of your virtual machine, you cannot login. what you do is replace the public/private key pair with a new pair. Here is how I fixed it.

1. Generate a new key pair on azure, by searching ssh on azure console
2. download the private key and save it. azure doesn't save private keys.
3. In the vm page, find change password, copy the public key which is saved by azure key resource, and finish the form
4. I restarted. then connect via ssh -i private_key azureuser@ip